﻿//////////////////////////////////////////////////////////////////////
// <copyright file=MaxHeap.cs">
//     Copyright (c) 2010
//     Released under  GNU GENERAL PUBLIC LICENSE
//     http://dev.perl.org/licenses/gpl1.html
// </copyright>
// <date> 3/30/2010 12:29:54 PM </date>
// <author> B. Endrovski </author>
// <web> http://furiouspixels.blogspot.com/ </web>
//////////////////////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ContourReconstruction
{
	/// <summary>
	/// Binary Heap based on the materials in the book "Data Structures and Algorithms
	/// with Object-Oriented Design Patterns" by Bruno R. Preiss
	/// </summary>
	/// <typeparam name="T">Anything that has a defined metric to alow sorting</typeparam>
	public class BinaryMaxHeap<T> : IEnumerable<T>, IEnumerator<T> where T : IComparable<T>
	{
		protected T[] array;
		protected HashSet<int> set;
		protected int current;

		public IComparer<T> Comparer
		{ get; set; }
		
		/// <summary>
		/// Number of elements in the heap
		/// </summary>
		public int Count
		{ get; protected set; }		

		public BinaryMaxHeap(int size)		
		{
			array = new T[size + 1];		// first location not in use
			set = new HashSet<int>();
			Count = 0;
			//
			current = 1;
		}

		public void Clear()
		{
			Count = 0;
			// Type not nullable!
			// GC will clean when overwriten
		}

		public void Enqueue(T obj)
		{
			// Add each element exatcly ones
			if (set.Contains(obj.GetHashCode()))
				return;
			else
				set.Add(obj.GetHashCode());

			if (Count == array.Length - 1)
				throw new ArgumentException("Heap totally full. Seriously!");
			++Count;
			int i = Count;
			while (i > 1 && array[i / 2].CompareTo(obj) < 0)
			{
				array[i] = array[i / 2];
				i /= 2;
			}
			array[i] = obj;
		}

		public T Min
		{
			get
			{
				if (Count == 0)
					throw new Exception("Heap is empty.");
				return array[1];
			}
		}

		public T DequeueMax()
		{
			if (Count == 0)
				throw new Exception("Heap is empty.");
			T result = array[1];
			T last = array[Count--];
			
			int i = 1;
			while (2 * i < Count + 1)
			{
				int child = 2 * i;
				if (child + 1 < Count + 1
				&& array[child + 1].CompareTo(array[child]) > 0)
					child += 1;
				if (last.CompareTo(array[child]) >= 0)
					break;
				array[i] = array[child];
				i = child;
			}
			array[i] = last;
			return result;
		}

		public bool IsEmpty
		{
			get { return Count == 0; }
		}

		public IEnumerator<T> GetEnumerator()
		{
			return this;
		}


		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return this;
		}

		#region IEnumerator<T> Members

		public T Current
		{
			get { return array[current]; }
		}

		#endregion

		#region IDisposable Members

		public void Dispose()
		{
			current = 0;
		}

		#endregion

		#region IEnumerator Members

		object System.Collections.IEnumerator.Current
		{
			get { throw new NotImplementedException(); }
		}

		public bool MoveNext()
		{
			++current;
			if (current < Count)
				return true;
			return false;
		}

		public void Reset()
		{
			current = 0;
		}

		#endregion
	} // end class
}
